|
The ω-regular languages are a class of ω-languages which generalize the definition of regular languages to infinite words. Büchi showed in 1962 that ω-regular languages are precisely the ones definable in a particular monadic second-order logic called S2S. == Formal definition == An ω-language L is ω-regular if it has the form * ''A''ω where A is a nonempty regular language not containing the empty string * ''AB'', the concatenation of a regular language ''A'' and an ω-regular language ''B'' (Note that ''BA'' is ''not'' well-defined) * ''A''∪''B'' where ''A'' and ''B'' are ω-regular languages (this rule can only be applied finitely many times) The elements of ''A''ω are obtained by concatenating words from ''A'' infinitely many times. Note that if ''A'' is regular, ''A''ω is not necessarily ω-regular, since ''A'' could be , the set containing only the empty string, in which case ''A''ω=''A'', which is not an ω-language and therefore not an ω-regular language. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Omega-regular language」の詳細全文を読む スポンサード リンク
|